/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
/* 
为了找出候选数组中所有和为目标值的不同组合，可以使用回溯法。
由于每个数字可以无限制重复选取，回溯时需注意从当前位置继续选择，避免重复组合。

方法思路
排序优化：先对候选数组排序，以便在回溯过程中提前剪枝。
回溯递归：维护当前路径和剩余目标值，递归选择当前位置及之后的数字，更新剩余目标值。
剪枝条件：若当前数字大于剩余目标值，停止后续选择；若剩余目标值为 0，记录当前路径。
*/
var combinationSum = function (candidates, target) {
  const result = [];
  candidates.sort((a, b) => a - b); // 排序以便剪枝

  // 回溯函数：start表示当前可选的起始位置，path表示当前组合，remaining表示剩余目标值
  const backtrack = (start, path, remaining) => {
    if (remaining === 0) {
      result.push([...path]); // 找到有效组合
      return;
    }

    for (let i = start; i < candidates.length; i++) {
      const num = candidates[i];
      if (num > remaining) break; // 剪枝：当前数字大于剩余目标值

      path.push(num);
      backtrack(i, path, remaining - num); // 允许重复选择当前数字
      path.pop(); // 回溯，撤销选择
    }
  };

  backtrack(0, [], target);
  return result;
};